Convex conjugate

In mathematics, convex conjugation is a generalization of the Legendre transformation. It is also known as Legendre–Fenchel transformation or Fenchel transformation (after Adrien-Marie Legendre and Werner Fenchel).

Contents

Definition

Let X be a real normed vector space, and let X^{*} be the dual space to X. Denote the dual pairing by

\langle \cdot , \cdot \rangle�: X^{*} \times X \to \mathbb{R}.

For a functional

f�: X \to \mathbb{R} \cup \{ %2B \infty \}

taking values on the extended real number line the convex conjugate

f^\star�: X^{*} \to \mathbb{R} \cup \{ %2B \infty \}

is defined in terms of the supremum by

f^{\star} \left( x^{*} \right)�:= \sup \left \{ \left. \left\langle x^{*} , x \right\rangle - f \left( x \right) \right| x \in X \right\},

or, equivalently, in terms of the infimum by

f^{\star} \left( x^{*} \right)�:= - \inf \left \{ \left. f \left( x \right) - \left\langle x^{*} , x \right\rangle \right| x \in X \right\}.

This definition can be interpreted as an encoding of the convex hull of the function's epigraph in terms of its supporting hyperplanes. [1]

Examples

The convex conjugate of an affine function

f(x) = \left\langle a,x \right\rangle - b,\, a \in \mathbb{R}^n, b \in \mathbb{R}

is

f^\star\left(x^{*} \right) = \begin{cases} b, & x^{*} = a \\ %2B\infty, & x^{*} \ne a. \end{cases}

The convex conjugate of a power function

f(x) = \frac{1}{p}|x|^p,\,1<p<\infty

is

f^\star\left(x^{*} \right) = \frac{1}{q}|x^{*}|^q,\,1<q<\infty

where \tfrac{1}{p} %2B \tfrac{1}{q} = 1.

The convex conjugate of the absolute value function

f(x) = \left| x \right|

is

f^\star\left(x^{*} \right) = \begin{cases} 0, & \left|x^{*} \right| \le 1 \\ \infty, & \left|x^{*} \right| > 1. \end{cases}

The convex conjugate of the exponential function f(x)=\,\! e^x is

f^\star\left(x^{*} \right) = \begin{cases} x^{*} \ln x^{*} - x^{*} , & x^{*} > 0 \\ 0 , & x^{*} = 0 \\ \infty , & x^{*} < 0. \end{cases}

Convex conjugate and Legendre transform of the exponential function agree except that the domain of the convex conjugate is strictly larger as the Legendre transform is only defined for positive real numbers.

Connection with average value at risk

Let F denote a cumulative distribution function of a random variable X. Then

f(x):= \int_{-\infty}^x F(u)\,du = \operatorname{E}\left[\max(0,x-X)\right] = x-\operatorname{E} \left[\min(x,X)\right]

has the convex conjugate

\begin{align} f^\star(p)=\int_0^p F^{-1}(q) \, dq & = (p-1)F^{-1}(p)%2B\operatorname{E}\left[\min(F^{-1}(p),X)\right] \\ & = p F^{-1}(p)-\operatorname{E}\left[\max(0,F^{-1}(p)-X)\right].\end{align}

Ordering

A particular interpretation has the transform

f^\text{inc}(x):= \arg \sup_t \,t\cdot x-\int_0^1 \max\{t-f(u),0\} \, \mathrm d u,

as this is a nondecreasing rearrangement of the initial function f; in particular, f^\text{inc}= f for ƒ nondecreasing.

Properties

The convex conjugate of a closed convex function is again a closed convex function. The convex conjugate of a polyhedral convex function (a convex function with polyhedral epigraph) is again a polyhedral convex function.

Convex-conjugation is order-reversing: if f \le g then f^* \ge g^*. Here

(f \le g )�:\iff (\forall x, f(x) \le g(x)).

Biconjugate

The convex conjugate of a function is always lower semi-continuous. The biconjugate f^{**} (the convex conjugate of the convex conjugate) is also the closed convex hull, i.e. the largest lower semi-continuous convex function with f^{**}\le f. For proper functions f, f = f** if and only if f is convex and lower semi-continuous.

Fenchel's inequality

For any function f and its convex conjugate f* Fenchel's inequality (also known as the Fenchel-Young inequality) holds for every x \in X and p \in X^*:

\left\langle p,x \right\rangle \le f(x) %2B f^\star(p).

Maximizing argument

It is interesting to observe that the derivative of the function is the maximizing argument to compute the convex conjugate:

f^\prime(x) = x^*(x):= \arg\sup_{x^\star} \langle x, x^\star\rangle -f^\star(x^\star) and
f^{\star\prime}(x^\star) = x(x^\star):= \arg\sup_x \langle x, x^\star\rangle-f(x);

whence

x= \nabla f^{\star}(\nabla f(x)),
x^\star= \nabla f(\nabla f^{\star}(x^\star)),

and moreover

f^{\prime\prime}(x) \cdot f^{\star\prime\prime} (x^\star(x))=1,
f^{\star\prime\prime}(x^\star)\cdot f^{\prime\prime}(x(x^\star))=1.

Scaling properties

If, for some \beta>0, \,g(x)=\alpha%2B \beta \cdot f(\gamma x%2B\delta), then

g^\star(x^\star)= -\alpha- \frac\delta\gamma x^\star %2B\beta \cdot f^\star \left(\frac {x^\star}{\beta \gamma}\right).

In case of an additional parameter (α, say) moreover

f_\alpha(x)=-f_\alpha(\tilde x),

where \tilde x is chosen to be the maximizing argument.

Behavior under linear transformations

Let A be a linear transformation from Rn to Rm. For any convex function f on Rn, one has

\left(A f\right)^\star = f^\star A^\star

where A* is the adjoint operator of A defined by

\left \langle Ax, y^\star \right \rangle = \left \langle x, A^\star y^\star \right \rangle.

A closed convex function f is symmetric with respect to a given set G of orthogonal linear transformations,

f\left(A x\right) = f(x), \; \forall x, \; \forall A \in G

if and only if its convex conjugate f* is symmetric with respect to G.

Infimal convolution

The infimal convolution of two functions f and g is defined as

\left(f \star_\inf g\right)(x) = \inf \left \{ f(x-y) %2B g(y) \, | \, y \in \mathbb{R}^n \right \}.

Let f1, …, fm be proper convex functions on Rn. Then

\left( f_1 \star_\inf \cdots \star_\inf f_m \right)^\star = f_1^\star %2B \cdots %2B f_m^\star.

The infimal convolution of two functions has a geometric interpretation: The (strict) epigraph of the infimal convolution of two functions is the Minkowski sum of the (strict) epigraphs of those functions.[1]

See also

References

  1. ^ Bauschke, Heinz H.; Goebel, Rafal; Lucet, Yves; Wang, Xianfu (2008). "The Proximal Average: Basic Theory". SIAM Journal on Optimization 19 (2): 766. doi:10.1137/070687542. 

External links